package com.xieyong.leetcode;

import java.util.*;

public class Leetcode1061 {
    public static void main(String[] args) {
        Leetcode1061 obj = new Leetcode1061();
        String s1 = "gicimlheddadmbmhiimakmhgklliljllfgjegamichefljcdef";
        String s2 = "jgjbjkhkliegkfdcbfcdgmeadlkgcdfkcjdmmcgliegijgjimj";
        String baseStr = "lqppdcmgachdannbaeztqoqfpimyzcdqksykgwymceogkgruey";
        String s = obj.smallestEquivalentString(s1, s2, baseStr);
        System.out.println(s);
    }


    public String smallestEquivalentString(String s1, String s2, String baseStr) {
        List<Set<Character>> firstlist = new ArrayList<>();
        for (int i = 0; i < s1.length(); i++) {
            char c1 = s1.charAt(i);
            char c2 = s2.charAt(i);
            int flag = 0;
            for (Set<Character> set : firstlist) {
                if (set.contains(c1) || set.contains(c2)) {
                    flag = 1;
                    set.add(c1);
                    set.add(c2);
                }
            }
            if (flag == 0) {
                Set<Character> set = new HashSet<>();
                set.add(c1);
                set.add(c2);
                firstlist.add(set);
            }
        }
//        更新传递性
        List<Set<Character>> list = new ArrayList<>();
        for (Set<Character> set : firstlist) {
            if(list.isEmpty()){
                list.add(set);
            } else {
                int flag = 0;
                for (Set<Character> set2 : list) {
                    if (setIsEqual(set, set2)) {
                        flag = 1;
                        set2.addAll(set);
                        break;
                    }
                }
                if (flag == 0) {
                    list.add(set);
                }
            }
        }
        System.out.println(list);
//        分别找出每个字母对应的最小字典序字母
        Map<Character,Character> resmap = new HashMap<>();
        for (Set<Character> set : list) {
            char min = 'z';
            for (Character c : set) {
                if (min >= c) {
                    min = c;
                }
            }
            for (Character c : set) {
                resmap.put(c,min);
            }
        }
//        用字典替换
        StringBuilder res = new StringBuilder();
        for (int i = 0; i < baseStr.length(); i++) {
            char c1 = baseStr.charAt(i);
            if(resmap.containsKey(c1)) {
                res.append(resmap.get(c1));
            } else {
                res.append(c1);
            }
        }
        return res.toString();
    }

    private boolean setIsEqual(Set<Character> set, Set<Character> set2) {
        for (Character c : set) {
            for (Character c2 : set2) {
                if (c == c2) return true;
            }
        }
        return false;
    }
}

//Map<Character, List<Character>> map = new HashMap<>();
//        for (int i = 0; i < s1.length(); i++) {
//char c1 = s1.charAt(i);
//char c2 = s2.charAt(i);
//            if (!map.containsKey(c1)) {
//List<Character> list = new ArrayList<>();
//                list.add(c1);
//                list.add(c2);
//                map.put(c1, list);
//            } else {
//List<Character> list = map.get(c1);
//                list.add(c2);
//                map.put(c1, list);
//            }
//                    if (!map.containsKey(c2)) {
//List<Character> list = new ArrayList<>();
//                list.add(c1);
//                list.add(c2);
//                map.put(c2, list);
//            } else {
//List<Character> list = map.get(c2);
//                list.add(c1);
//                map.put(c2, list);
//            }
//                    }
////        添加传递性
//List<Set<Character>> list2 = new ArrayList<>();
//        for (Map.Entry<Character, List<Character>> entry : map.entrySet()) {
//Character key = entry.getKey();
//List<Character> values = entry.getValue();
//int flag = 0;
//            for (Set<Character> set : list2) {
//        if (set.contains(key)) {
//flag = 1;
//        set.addAll(values);
//                }
//                        }
//                        if (flag == 0) {
//        list2.add(new HashSet<>(values));
//        }
//        }
//        System.out.println(list2);